#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include "stack.h"
void swap(int* as, int* aq)
{
	int tmp = *as;
	*as = *aq;
	*aq = tmp;
}
int sanshuquzhong(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] > a[right])
	{
		if (a[mid] > a[left])
		{
			return left;
		}
		else if (a[mid] > a[right])
		{
			return mid;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[mid] > a[right])
		{
			return right;
		}
		else if (a[mid] > a[left])
		{
			return mid;
		}
		else
		{
			return left;
		}
	}
}
int yici(int* a, int left, int right)
{
	int mid = sanshuquzhong(a, left, right);
	swap(&a[mid], &a[left]);
	int key = left;
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		if (a[cur] < a[key] && ++prev != cur)
		{
			swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	swap(&a[prev], &a[key]);
	return prev;
	
}
void kuaisupaixu(int* a, int left, int right)
{
	Stack as;
	StackInit(&as);
	StackPush(&as, right);
	StackPush(&as, left);
	while (!StackEmpty(&as))
	{
		int begin = StackTop(&as);
		StackPop(&as);
		int end = StackTop(&as);
		StackPop(&as);
		int key=yici(a, begin, end);
		if (key + 1 < end)
		{
			StackPush(&as, end);
			StackPush(&as, key + 1);
		}
		if (begin < key - 1)
		{
			StackPush(&as, key - 1);
			StackPush(&as, begin);
		}
	}
	StackDestroy(&as);
}
int main()
{
	int arr[] = { 2352,433,4624,57,536473,568,345768,4769,8759,56,186797658,46,96,572,457,7,9578,23423,5,4256,56,4526,457,64256,765,765,387,635876748989,9476589,4678936,724,674,5612,6,2457,2546,72 };
	kuaisupaixu(arr, 0, sizeof(arr) / sizeof(arr[0])-1);
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d", arr[i]);
		printf("\n");
	}

	return 0;
}